1. Field of the Invention
This invention relates generally to the field of digital signal processing and, more particularly, to a system and method for operating on data values so that their average (with respect to time and/or space) survives truncation.
2. Description of the Related Art
Modern computer systems typically rely on a graphics system to generate output video signals for the display devices. Early graphics systems were only responsible for receiving data produced by the host processor and displaying it on a monitor device. In essence, they acted as simple translators or interfaces. Modern graphics systems, however, incorporate graphics processors with a great deal of processing power. They now act more like coprocessors rather than simple translators. This change has resulted in an increase in both the complexity and amount of data being sent to the display devices. For example, modern display devices have many more pixels, greater color depth, and are able to display more complex images with higher refresh rates than earlier models. Similarly, the images displayed are now more complex and may involve advanced techniques such as anti-aliasing and texture mapping.
As a result, without considerable processing power in the graphics system, the host processor would spend a great deal of time performing graphics calculations. This could rob the host processor of the processing power needed for performing other tasks associated with program execution, and thereby dramatically reduce the overall performance of the computer system. With a powerful graphics system, however, when the host processor is instructed to draw a box on the screen, the host processor may send a request to the graphics system stating “draw a box at these coordinates.” The graphics system may then compute the position and color of each pixel comprising the box. The host processor is thus liberated from the time consuming draw or render process.
Generally, a graphics system is a type of video adapter that contains its own processor to boost performance levels. These processors are specialized for computing graphical transformations, and thus, they tend to achieve better results than the general-purpose CPU used by the computer system. In addition, they free up the computer's CPU to execute other commands while the graphics system is handling graphics computations. The popularity of graphical applications, and especially multimedia applications, has made high performance graphics systems a common feature of computer systems. Most computer manufacturers now bundle a high performance graphics system with their computer systems.
Since graphics systems typically perform only a limited set of functions, they may be customized and therefore are far more efficient at graphics operations than the computer's general-purpose CPU. While early graphics systems were limited to performing two-dimensional (2D) graphics, their functionality has increased to support three-dimensional (3D) wire-frame graphics, 3D solids, and now includes support for three-dimensional (3D) graphics with textures and special effects such as advanced shading, fogging, alpha-blending, and specular highlighting.
Prior art graphics systems use a conventional frame buffer for refreshing pixel/video data on a display device (e.g. a monitor device or projection device). The frame buffer stores rows and columns of pixels that exactly correspond to respective row and column locations on the display device. Prior art graphics systems render 2D and/or 3D images or objects into the frame buffer in pixel form, and then read the pixels from the frame buffer during a screen refresh to refresh the display device. Thus, the frame buffer stores the output pixels that are provided to the display device. To reduce visual artifacts that may be created by refreshing the screen at the same time the frame buffer is being updated, frame buffers in most graphics systems are double-buffered.
To obtain more realistic images, some prior art graphics systems have gone further by generating more than one sample per pixel. As used herein, the term “sample” refers to information calculated at a particular point on an object or image, i.e. information such as one or more of color, depth (z), transparency, etc. For example a sample may comprise the following component values: a red value, a green value, a blue value, a z-depth value, and an alpha value (e.g., representing the transparency of the sample). A sample may also comprise other information, e.g, a blur value, an intensity value, brighter-than-bright information, and an indicator that the sample partially or completely comprises control information rather than color information (i.e., “sample control information”). By calculating more samples than pixels (i.e., super-sampling), a more detailed image is calculated than can be displayed on the display device. For example, a graphics system may calculate four samples for each pixel to be output to the display device. After the samples are calculated, they are then combined or filtered to form the pixels that are stored in the frame buffer and then conveyed to the display device. Using pixels formed in this manner may create a more realistic final image because overly abrupt changes in the image may be smoothed by the filtering process.
These prior art super-sampling systems typically generate a number of samples that are far greater than the number of pixel locations on the display. These prior art systems typically have rendering processors that calculate the samples and store them into a render buffer. Filtering hardware then reads the samples from the render buffer, filters the samples to create pixels, and then stores the pixels in a conventional frame buffer. The conventional frame buffer is typically double-buffered, with one side being used for refreshing the display device while the other side is updated by the filtering hardware. These systems, however, have generally suffered from limitations imposed by the conventional frame buffer, and by the added latency caused by the render buffer and filtering hardware. Therefore, an improved graphics system is desired which includes the benefits of pixel super-sampling while avoiding the drawbacks of the conventional frame buffer.
One of the factors determining the quality of the video output generated by a display device as perceived by humans is the number NQ of bits of precision delivered to the display device per pixel per color value by the graphics system. A number of adverse perceptual effects may be observed when the value NQ is not sufficiently large. For example, with 24-bit color, i.e. eight bits each for red, green and blue, a smoothly varying color field may appear stair-stepped. (Experimental evidence indicates that the limit of human perceptual sensitivity is approximately 12 bits of linear quantization for the lighting conditions likely to prevail in typical display applications. It is noted that under some very special conditions human perceptual sensitivity has been demonstrated up to approximately 13 bits.) Thus, increasing the value NQ is generally desirable. However, a larger value for NQ implies a larger and more costly pixel frame buffer. It may be difficult for a graphics system to realize a value for NQ which is large enough to eliminate (or sufficiently reduce) the adverse perceptual effects since the associated memory costs may be high. In certain situations, the video output generated by a graphics system may be targeted for a non-human sensing system. For example, the video output may used to train another computer system such as a machine vision system. Thus, there may be a demand for the graphics system to generate bit precisions (for pixel color or intensity) higher than the limit of human perceptual sensitivity. Therefore, there exists a need for a system and method capable of delivering increased pixel color (or intensity) precision from lower precision sample color values.
More broadly, in the field of signal processing, there exists a problem that may be stated as follows. Suppose that there exists a collection of data values each having a precision of K bits. Suppose that each of the data values are rounded to L bits, where L is smaller than K. Suppose that a processing unit computes a weighted average AVGrnd of the rounded data values. If the same weighted average computation were performed on the original collection of K-bit data values, resulting in an average value AVGorig, it would be readily observed that the two averages, AVGrnd and AVGorig, differ significantly. In other words, the average of a set of data values is not generally preserved through a rounding operation. Thus, there exists a need for a system and method which could modify the data values so that the average of the rounded data values after modification would more closely approximate the true average AVGorig of the original K-bit data values.
It has been observed that biological systems are capable of providing increased signal sensitivity by an appropriate use of noise. This phenomenon, known as “stochastic resonance”, is described in the following references:                (1) J. J. Collins, T. T. Imhoff, and P. Grigg, 1996, “Noise enhanced tactile sensation”, Nature 383(October 31):769; and        (2) F. J. Gluckman, W. L. Ditto, M. L. Spano, and S. J. Schiff, 1996, “Stochastic resonance in a neuronal network from mammalian brain”, Physical Review Letters 77(November 4):4098.The signal processing technique known as dithering may be considered as a form a stochastic resonance. Dithering has been applied in the field of software rendering to address the problem of false contouring. For example, there exists a rendering package known as Renderman® that includes an algorithm for dithering an array of pixel values. See pages 184-185 of “The Renderman Companion” by Steve Upstill, 1990, Addison Wesley Publishing. However, traditional attempts at dithering have typically been limited to off-line, software applications. Thus, there exists a need for a system and method capable of correcting the problem of false contouring in real-time, and more particularly, in the context of a real-time supersampled graphics system.        